In the field of computer program testing, different approaches have been developed to more accurately and completely test program function. For example, control-flow-based test generation seeks to cover at a minimum all the statements or branches in a program (“statement coverage” or “branch coverage”). In multiple condition coverage, each possible condition of each statement is tested at a local level. For example, in a statement of the form if (x∥y) then a else b, multiple condition coverage would locally test whether the statement performs as expected where x is true and y is false, where y is true and x is false, where both x and y are true, or where both x and y are false. Path coverage is an extension of multiple condition coverage that seeks to test all possible paths through a program. The idea of using paths and symbolic execution of paths to generate tests has a long and rich history going back to the mid-1970's and continuing to the present day. See, e.g., Boyer et al., “SELECT—A Formal System for Testing and Debugging Programs by Symbolic Execution,” SIGPLAN Notices, 10(6):234-245 (1975); Howden, “Reliability of the Path Analysis Testing Strategy,” IEEE Trans. on Software Engineering, 2:208-215 (1976); Clarke, “A System to Generate Test Data and Symbolically Execute Programs,” IEEE Trans. on Software Engineering, 2(3):215-222 (1976); Jasper et al., “Test Data Generation and Feasible Path Analysis,” Proc. Int'l Symposium on Software Testing and Analysis, 95-107 (1994); Gotlieb et al., “Automatic Test Data Generation Using Constraint Solving Techniques,” Proc. Int'l Symposium on Software Testing and Analysis, 53-62 (1998); Gupta et al., “Automated Test Data Generation Using an Iterative Relaxation Method,” FSE 98: Foundations of Software Engineering (1998). Path coverage is notoriously difficult to work with as a coverage metric because there are an unbounded number of paths in programs with loops, which characterizes most existing non-trivial programs.
A classic problem in path-based symbolic execution is the selection of program paths. One way to guide the search for feasible paths is to execute the program symbolically along all paths, while guiding the exploration to achieve high code coverage. Clearly, it is not possible to symbolically execute all paths, so the search must be cut off at some point. Often, tools will simply analyze loops through one or two iterations. See Bush et al., “A Static Analyzer for Finding Dynamic Programming Errors,” Software—Practice and Experience, 30(7):775-802 (2000). Another way to limit the search is to bound the size of the input domain (say, to consider arrays of at most length three) or to bound the maximum path length that will be considered, as done in bounded model checking. See, e.g., Jackson et al., “Finding Bugs with a Constraint Solver,” Proc. Int'l Symposium on Software Testing and Analysis, 14-25 (2000). An experiment by Yates and Malevris provided evidence that the likelihood that a path is feasible decreases as the number of predicates in the path increases. This led them to use shortest-path algorithms to find a set of paths that covers all branches in a function. See Yates et al., “Reducing the Effects of Infeasible Paths in Branch Testing,” Proc. Symposium on Software Testing, Analysis, and Verification, 48-54 (1989).
Automatically created Boolean program abstraction can be used to analyze program behavior. See, e.g., Graf et al., “Construction of Abstract State Graphs with PVS,” CAV 97: Computer-aided Verification, 72-83 (1997); Ball et al., “Automatic Predicate Abstraction of C programs,” PLDI 01: Programming Language Design and Implementation, 203-213 (2001).
Other approaches to test generation rely on dynamic schemes. Given an existing test t, Korel's “goal-oriented” approach seeks to perturb t to a test t′ covering a particular statement, branch or path using function minimization techniques. See Korel, “Dynamic Method of Software Test Data Generation,” Software Testing, Verification and Reliability, 2(4):203-213, (1992). The potential benefit of Korel's approach is that it is dynamic and has an accurate view of memory and flow dependences. The downside of Korel's approach is that test t may be very far away from a suitable test t′.
Another approach to test generation is found in the Korat tool. See Boyapati et al., “Korat: Automated Testing Based on Java Predicates,” Proc. Int'l Symposium on Software Testing and Analysis, 123-133 (2002). This tool uses a function's precondition on its input to automatically generate all (non-isomorphic) test cases up to a given small size. It exhaustively explores the input space of the precondition and prunes large portions of the search space by monitoring the execution of the precondition. For a program that has no constraints on its input, the Korat method may not work very well. Furthermore, it requires the user to supply a bound on the input size.
Work on three-valued model checking by Bruns, Godefroid, Huth and Jagadeesan shows how to model incomplete (abstract) systems using modal transition systems (equivalently, partial Kripke Structures). See, e.g., Bruns et al., “Model Checking Partial State Spaces with 3-valued Temporal Logics,” CAV 99: Computer Aided Verification, 274-287 (1999); Godefroid et al., “Abstraction-based Model Checking Using Modal Transition Systems,” CONCUR 01: Conf. on Concurrency Theory, 426-440 (2001). Their work gives algorithms for model checking temporal logic formulae with respect to such systems.
Random or fuzz testing is another popular technique for unit testing. See, e.g., Ntafos, “On Random and Partition Testing,” Proc. Int'l Symposium on Software Testing and Analysis, 42-48 (1998).
Of course, if a designer provides a specification of the expected behavior of a software system, this specification can be used to drive test generation as well.
Although it is useful to know whether a statement in a program functions correctly when it is tested at a local level, it is also useful to know whether the behavior of the statement is still appropriate as the state of the computer program changes over time. However, because path coverage is not achievable in most programs, there exists a need for test generation techniques and tools that improve upon statement coverage or multiple condition coverage while working within a finite set of program states.